package com.lihepeng.leecode.recursive;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 子集问题
 * 通过回溯法完成
 * Solution78 关联
 * 可以重复选择
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 *
 */
public class Solution90 {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList item = new LinkedList();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 先进行排序 将两个相近的数值放到一块
        Arrays.sort(nums);
        dfs(nums,0);
        return result;
    }

    /**
     * 类似于原来的 不过需要对输入集合做减枝 路径上面两个重合的既做一个
     *
     * @param nums
     * @param begain
     */
    private void dfs(int []nums,int begain) {
        result.add(new ArrayList<>(item));
        for (int i=begain;i<nums.length;i++)  {
            // 减枝操作
            if (i>begain && nums[i] == nums[i-1]) {
                continue;
            }
            item.addLast(nums[i]);
            dfs(nums,i+1);
            item.removeLast();
        }
    }
}
